double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k+1,vector<vector<double>>(n+4,vector<double>(n+4)));
        int dirs[8][2]={{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
        for(int i=2;i<n+2;++i)
        {
            fill(dp[0][i].begin()+2,dp[0][i].begin()+n+2,1);
        }

        for(int step=1;step<=k;++step)
        {
            for(int i=2;i<n+2;++i)
            {
                for(int j=2;j<n+2;++j)
                {
                    for(auto& [dx,dy]:dirs)
                    {
                        dp[step][i][j]+=dp[step-1][i+dx][j+dy];
                    }
                    dp[step][i][j]/=8;
                }
            }
        }

        return dp[k][row+2][column+2];
    }